import copy
class SQListDemo:
	'''冒泡排序 类型'''
	def __init__(self, list=None):
		'''初始化需要排序的列表'''
		self.list = list 

	def swap(self,i,j):
		'''交换指定的两个元素值'''
		temp = self.list[i]
		self.list[i] = self.list[j]
		self.list[j] = temp

	def sort(self):
		'''最简单的排序'''
		length = len(self.list)
		list = self.list
		count = 0
		swapcount = 0
		for i in range(length):
			for j in range(length):
				count = count + 1
				if list[i] < list[j]:
					swapcount = swapcount + 1
					self.swap(i,j)
		return count,swapcount

	def sort1(self):
		'''最简单的排序升级
		因为当完成了第 N 次循环后，那么这个列表的前 N 个实际上已经排好序了
		所以不需要在进行循环判断，改函数优化这个一个点
		'''
		length = len(self.list)
		list = self.list
		count = 0
		swapcount = 0
		for i in range(length):
			for j in range(i,length):
				count = count + 1
				if list[i] > list[j]:
					swapcount = swapcount + 1
					self.swap(i,j)
		return count,swapcount

	def sort2(self):
		'''sort1 进一步优化
		上面的实际上优化的已经可以了，但是这个排序还是不够稳定
		如果一个列表已经是一个排好序的列表， sort1 还是需要循环很多次
		所以这个优化优化的是冒泡排序的稳定性
		'''
		length = len(self.list)
		list = self.list
		count = 0
		swapcount = 0
		flag = False
		for i in range(length):
			if flag:
				return count,swapcount
			flag = True
			for j in range(i,length):
				count = count + 1
				if list[i] > list[j]:
					flag = False
					swapcount = swapcount + 1
					self.swap(i,j)
		return count,swapcount


	def sort3(self):
		'''对于 sort2 的代码继续优化
		sort2 的代码 每次循环的时候 第 N 个元素都要和第 N 个元素进行一个判断
		实际上这个操作是没有必要的。
		'''
		length = len(self.list)
		list = self.list
		count = 0
		swapcount = 0
		flag = True
		i = 0
		while i < length and flag:
			flag = False
			j = length - 2
			while j >= i:
				count += 1
				if list[j] > list[j + 1]:
					self.swap(j, j + 1)
					flag = True
					swapcount += 1
				j -= 1
			i += 1
		return count,swapcount

	def sort4(self):
		'''sort4 == sort3
		主要是用来梳理整个排序的逻辑
		'''
		#获取列表的长度
		length = len(self.list)
		#获取到列表的引用，这里主要是为了方便后续的操作
		list = self.list
		#记录整个排序循环了多少次
		count = 0
		#记录整个排序元素交换的次数
		swapcount = 0
		#如果 flag 为 False 会自动退出当前的循环
		flag = True
		#初始化一个 i = 0 的变量
		i = 0
		#只要满足 i < 列表长度，并且 flag == True
		while i < length and flag:
			flag = False
			#j = 列表长度 - 2 因为列表的下标是从 0 开始的，所以这里需要 - 2
			j = length - 2
			#只要 j 的值大于等于 i 就满足继续执行的条件
			while j >= i:
				count += 1
				#list[j] 就是最后第二个元素 ，list[j + 1]就是最后一个元素
				#如果最后一个元素小于最后第二个元素，继续执行后续操作
				if list[j] > list[j + 1]:
					#交换元素位置，根据上面的逻辑，把最小的元素放到前面
					self.swap(j, j + 1)
					flag = True
					swapcount += 1
				j -= 1
			i += 1
		return count,swapcount

	def __str__(self):
		ret = ""
		for i in self.list:
			ret += " %s" % i
		return ret

	def line(self):
		print('{:-^60}'.format('分割线'))

if __name__ == "__main__":
	list1 = [7,51,213,122,34,41,95,6,717]
	#list1 = [1,2,3,4,5,6,7,8]
	print('冒泡函数 SQListDemo')
	demo = SQListDemo(copy.deepcopy(list1))
	count1,swapcount1 = demo.sort()
	print(demo.list)
	print("冒泡排序 {2} 循环了：{0} 次，元素交换了 {1} 次。".format(count1,swapcount1,'sort'))
	demo.line()

	demo = SQListDemo(copy.deepcopy(list1))
	count2,swapcount2 = demo.sort1()
	print(demo.list)
	print("冒泡排序 {2} 循环了：{0} 次，元素交换了 {1} 次。".format(count2,swapcount2,'sort1'))
	demo.line()
	
	demo = SQListDemo(copy.deepcopy(list1))
	count3,swapcount3 = demo.sort2()
	print(demo.list)
	print("冒泡排序 {2} 循环了：{0} 次，元素交换了 {1} 次。".format(count3,swapcount3,'sort2'))
	demo.line()

	demo = SQListDemo(copy.deepcopy(list1))
	count3,swapcount3 = demo.sort3()
	print(demo.list)
	print("冒泡排序 {2} 循环了：{0} 次，元素交换了 {1} 次。".format(count3,swapcount3,'sort3'))
	demo.line()